package lc.q1_50;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 *
 * candidates 中的数字可以无限制重复被选取。
 *
 * 说明：
 *
 * 所有数字（包括 target）都是正整数。
 * 解集不能包含重复的组合。 
 *
 */
public class Q39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        return combinationSum(candidates, 0, target);
    }

    public List<List<Integer>> combinationSum(int[] candidates, int start, int target) {
        List<List<Integer>> results = new ArrayList<>();
        for (int i = start; i < candidates.length; i++) {
            final int candidate = candidates[i];
            if (candidate == target) {
                final ArrayList<Integer> e = new ArrayList<>();
                e.add(candidate);
                results.add(e);
            } else if (candidate < target) {
                List<List<Integer>> remains = combinationSum(candidates, i, target - candidate);
                if (remains != null && remains.size() != 0) {
                    for (List<Integer> remain : remains) {
                        remain.add(0, candidate);
                    }
                    results.addAll(remains);
                }
            } else {
                break;
            }
        }
        return results;
    }

    public static void main(String[] args) {
        int[] candidates = new int[]{2,3,5};
        final Q39 q39 = new Q39();
        final List<List<Integer>> lists = q39.combinationSum(candidates, 8);
        System.out.println(lists);
    }


}
